//
//  32.把数组排成最小的数.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/21.
//

import Foundation
/*
 题目：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
 思路：1、使用api、2、自定义排序
 */
func offer_32() {
    print(Solution().printMinNumbe1([3,32,321]))
}

fileprivate class Solution {
    func printMinNumbe1(_ numbers: [Int]) -> String {
        var numbers = numbers
        numbers.sort { "\($0)\($1)" < "\($1)\($0)" }
        return numbers.map { "\($0)" }.joined()
    }
    
    func printMinNumbe2(_ numbers: [Int]) -> String {
        func partition(_ arr: inout [Int], left: Int, right: Int) -> Int {
            let pivot = arr[right]
            var i = left
            for j in left..<right {
                if "\(arr[j])\(pivot)" < "\(pivot)\(arr[j])" {
                    arr.swapAt(i, j)
                    i += 1
                }
            }
            arr.swapAt(i, right)
            return i
        }
        func sort(_ arr: inout [Int], _ l: Int, _ r: Int) {
            if l >= r { return }
            // 创建栈
            var stack = Stack<(Int, Int)>()
            stack.push(element: (l, r))
            while stack.count > 0 {
                let (a, b) = stack.pop()!
                if a < b {
                    let p = partition(&arr, left: a, right: b)
                    stack.push(element: (a, p - 1))
                    stack.push(element: (p + 1, b))
                }
            }
        }
        var numbers = numbers
        sort(&numbers, 0, numbers.count - 1)
        return numbers.map { "\($0)" }.joined()
    }
}

